/**
 * https://leetcode-cn.com/problems/minimum-window-substring/
 * 最小覆盖字串
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * @param s
 * @param t
 */
const minWindow = (s: string, t: string): string => {
  let l = 0,
    r = 0;

  const need: Record<string, number> = {};
  const win: Record<string, number> = {};

  // 初始化need 和 win
  for (let c of t) {
    need[c] = need[c] == undefined ? 1 : need[c] + 1;
    win[c] = 0;
  }
  const len = s.length;
  const sizes = Object.keys(need).length;

  let maxLen = Number.MAX_SAFE_INTEGER,
    left = 0,
    right = 0;

  let valid = 0;
  while (r < len) {
    const char = s[r];

    if (need[char]) {
      win[char]++; // 对应的窗口字段加1
      if (win[char] === need[char]) valid++;
    }

    // 往后移动(在前面目的是为了让r - l 刚好能等于长度)
    r++;
    // 长度到达了, 开始缩小窗口

    while (valid === sizes) {
      // 即将要移出的字符
      let char = s[l];

      // 更新找到的长度
      if (r - l < maxLen) {
        left = l;
        right = r;
        maxLen = right - left;
      }

      l++;

      if (need[char]) {
        // 一样, 有效的值就要缩短, r开始往后移动
        if (need[char] === win[char]) valid--;
        win[char]--; // 对应的窗口字段长度减1
      }
      //   console.log(win, r)
    }
  }

  return maxLen === Number.MAX_SAFE_INTEGER ? "" : s.slice(left, right);
};

console.log(minWindow("ADOBECODEBANC", "ABC"));
// console.log(minWindow("aa", "aa"));
